Sometimes it is desirable to find the closest point in a sample of points to an arbitrary point in high dimensional space. In many cases, an approximate value is sufficient, particularly n the field of image processing where speed is a consideration.
One example of such a case is scaling a palletized bitmap image using bilinear or trilinear scaling. In this example, desired color RGB values are computed and an efficient means must be found to obtain the nearest color in the limited existing palette of RGB values. In this case, one is looking for the closest point in three dimensions.
Another example is the idea of image compression, or upscaling, where there is a large library of 8×8 pixel block layouts. For compression, the image is divided into 8×8 pixel blocks, and a search is conducted for the nearest match in a 64-dimensional space from the library sample. Once found, the entire 8×8 block can be represented by an offset value into the library rather than 64 individual RGB values, giving a 64-1 lossy compression.
The most common method of obtaining the closest point is to use the formula for determining Euclidean distance and extrapolating it out to the number of dimensions required.This calculation takes the form of:       L    2    =            ∑              i        =        1            N        ⁢          x      i      2      where N is the number of dimensions and L is the distance.
This calculation must be done for each sample, determining the distance for each sample and then comparing the distance until the closest point is located. This method is accurate, but slow, particularly in multi-dimensional systems with large sample sizes. The method requires a large number of multiplications, which, on present-day computers, are generally slower than additions.
There are other methods, such as the use of Octrees or binary space partitioning, which generally provide fast searches, but which require a significant amount of preprocessing. This technique is not suitable for cases in which the sample is dynamically changing, or in cases where only a limited number of searches are needed.
A somewhat similar algorithm which is used extensively for nearest neighbor determination, generally in 3-dimensional space, is Octree Quantization which utilizes preprocessing of the sample to gain speed. The intention of Octree is very similar, although the technique is essentially different. A reference to this is in “Graphics Gems,” Volume I, Chapter IV, Color Quantization by Octree Quantization, by Gervautz and Purgathofer
U.S. Pat. No. 5,953,463, granted Sep. 14, 1999, to Tanaka et al., for Image processing method and image processing apparatus describes image processing wherein an image is divided into blocks, the various components of the blocks are detected, and wherein density of a target picture element is derived as a function of adjacent picture elements.